Essential to the fabrication of an integrated circuit based upon an integrated circuit design is the process of laying out component "cells" or circuit functions in the space available in an integrated circuit die. This process is also known as "floorplanning". Floorplanning is the process of placing functional devices (also referred to as: "cells", "functions", "modules", "elements", "blocks", or "functional blocks") on an integrated circuit die and allocating interconnection space between them, so as to minimize the actual die area required to encompass such cells and their interconnections, and to maximize the probability that such interconnections can be routed within that area.
Automated floorplanners are known in the art. An example of such a floorplanner is given in U.S. Pat. No. 4,918,614, "Hierarchical Floorplanner", issued Apr. 17, 1990 to Modarres (hereinafter "Modarres"), incorporated herein by reference.
Typically, an automated floorplanner will attempt to partition an integrated circuit die area into a number of smaller areas (sub-partitions) according to the relationships between cells in an integrated circuit design, and to assign those cells to those smaller areas in a fashion which will (hopefully) minimize the distance between cells which are highly connected (minimize wire routing problems) and which will minimize the total amount of die area required. Modarres described a technique whereby the partitioning and placement proceeds according to a design hierarchy, and is applied recursively to the design until the bottom level of the design is reached.
A commonly used partitioning technique is known as the "min-cut" algorithm, described in C. Fiduccia and R. Mattheyses, "A Linear-Time Heuristic for Improving Network Partitions," Proc. Design Automation Conference, 1982, p. 175, (hereinafter KLFM). One problem with the KLFM algorithm is that it is order-dependent, that is, the order in which cells are encountered by the algorithm affects the resultant partitioning.
A common approach to handling placement problems is to combine top-down and bottom-up techniques. The bottom-up approach is called "clustering", and involves grouping of the most highly connected cells in a design into "clusters" of cells. The goal of the top-down technique is to determine the locations for all of the clusters (placement). It is well known that "clustering" or grouping of related cells into "clusters" before cell placement can improve the quality of placement and reduce the run-time of an automated layout (floorplanning) system significantly. (The "clusters" are treated as "cells" for purposes of initial placement.)
Many approaches have been proposed for attacking the clustering problem. Known techniques in this area can be grouped into two major categories:
1) identification of clusters by naturally occurring relationships (e.g., connectivity) inherent in the integrated circuit design, and PA1 2) use of local connectivity information to help identify clusters. PA1 a) providing an integrated circuit die size and shape; PA1 b) defining within the integrated circuit die size and shape a layout area; PA1 c) providing an integrated circuit design including a plurality of cells and a plurality of inter-cell connections; said cells each having one or more connection points by which the inter-cell connections are accomplished; PA1 d) performing a global optimization process to arrive at an optimal placement of the cells within the layout area, and store coordinates of each cell in a "cluster" list, according to the placement; PA1 e) defining each cell in the "cluster" list as a "cluster"; PA1 f) identifying pairs of neighboring clusters according to the placement, computing a figure-of-merit for each pair of neighboring clusters, and storing an identifier and the computed figure-of-merit for each pair of neighboring clusters in a "pair" list; PA1 g) sorting the "pair" list according to the figure-of-merit; PA1 h) selecting and removing the "pair" list entry for a neighboring pair of clusters having a best figure-of-merit according to a pre-defined criterion, unless there is a "tie" where two or more entries in the "pair" list have equal (best) figures-of-merit, in that case breaking the tie by selecting and removing from the "pair" list the entry corresponding to a neighboring pair of clusters having the best figure-of-merit and having the least distance ("tie-breaker") between the clusters; PA1 i) proceeding to step "m" if the figure-of-merit for the selected neighboring pair of clusters fails to meets a pre-determined first constraint, otherwise proceeding to step "j"; PA1 j) proceeding to step "1" if the total number of cells within the neighboring pair of clusters fails to meet a pre-defined second constraint, otherwise proceeding to step "k"; PA1 k) forming a new cluster by merging the selected neighboring pair of clusters into a single cluster, updating the "cluster" list to include the new cluster and a set of coordinates for the new cluster, computing new figures-of-merit for new entries in the "pair" list which includes neighboring pairs of clusters which include the new cluster, eliminating entries in the "pair" list corresponding to any neighboring pair of cluster which includes either of the clusters in the selected neighboring pair, and re-sorting the pair list according to the figure of merit; PA1 l) proceeding to step "h" if there are any remaining entries in the "pair" list, otherwise proceeding to step m; PA1 m) completing a layout process based upon the integrated circuit design, the integrated circuit die size and shape, and die area partitioning and placement of the clusters of cells, said layout process resulting in an integrated circuit layout.
Examples of the first category of clustering approach (also known as "global optimization") are found in J. Garbers, H. J. Promel and A. Steger, "Finding Clusters in VLSI Circuits," Proc. Int. Conf. Computer-Aided-Design, 1990, pp. 520-523, (hereinafter "GPS90") and in L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio-Cut Partitioning and Clustering," UCLA CS Dept., TR-019973, October 1991 (hereinafter "HK91").
Global optimization has been widely used to help cell placement. Examples of this are found in R. S. Tsay, E. S. Kuh, and C. P. Hsu, "PROUD: A Fast Sea-Of-Gates Placement Algorithm," proc. Design Automation Conference, 1988, pp. 318-323 (hereinafter "TKH88"), H. J. Kappen and F. M. J. deBont, "An Efficient Placement Method for Large Standard-Cell and Sea-of-Gates Designs," EDAC, 1990, pp. 312-316 (hereinafter "KdB90"), J. M. Klenhans, G. Sigl, F. M. Johannes and K. J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Trans. on CAD, vol 10, no. 3, March, 1991, pp. 356-365 (hereinafter KSJA91), and J. Cong, L. Hagen and A. Kahng, "Net Partitions Yield Better Module Partitions," Proc. Design Automation Conference, 1992, pp. 47-52 (hereinafter "CHK92").
HK91 and CHK92 apply global optimization to partitions. In general, global optimization gives a global picture of the design, no matter whether the objective function of the global optimization is minimizing total wire length or finding the eigenvector of the second smallest eigenvalue.
GPS90 describes clustering based upon "k-connectedness" in graph theory. HK91 describes a technique whereby the value of an eigenvector corresponding to the second smallest eigenvalue is used to identify clusters. Although these global optimization techniques are relatively simple to implement, they have at least one major drawback in that clusters formed by this technique can vary greatly in size; a significant problem if those clusters are to be placed using conventional placement algorithms. Conventional placement algorithms approach placement by dividing areas (partitions) of a die into evenly sized sub-partitions. If cluster sizes are permitted to vary significantly, the "fit" of these clusters to the sub-partitions is considerably less than optimal, causing poor utilization of die area.
Examples of the second category of clustering approach are found in T. Ng, J. Oldfield, and V. Pitchumani, "Improvements of a Mincut Partition Algorithm," Proc. Int. Conf. Computer-Aided Design, 1987, pp. 470-473, (hereinafter NOP87) and in S. Mallela and L. K. Grover, "Clustering based Simulated Annealing for Standard Cell Placement," Proc. Design Automation Conference, 1988, pp. 312-317 (hereinafter MG88). Both NOP87 and MG88 describe identification of clusters by using local connectivity information. However, since local connectivity information is missing or hidden in very large designs, the performance of these techniques degrades as the designs to which they are applied become larger, again causing poor utilization of die area.